<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
</head>

<body>
    <script>
        // const arr = [2, 3, 5, 7, 4];
        const arr=[30,40,60,10,20,50];
        // const arr=[6, 1, 2, 7, 9, 3, 4, 5, 10, 8];
        // 1、升序，分治，递归
        // 2、注意边界条件，i<j
        // 3、注意需要从右到左先遍历
        /**
         * 基准值交换
         * [30,40,60,10,20,50];
         * 第一轮交换
         * 30,40,60,10,20,50
         *     ^        ^   
         * 第一轮交换结束
         * 30,20,60,10,40,50
         *     ^        ^
         * 第二轮交换
         * 30,20,60,10,40,50
         *        ^  ^      
         * 第二轮交换结束
         * 30,20,10,60,40,50
         *        ^  ^      
         * 第三轮交换,左右哨兵相遇，置换相遇位置与基准值
         * 30,20,10,60,40,50
         *        ^
         *        ^
         * 第三轮交换结束
         * 10,20,30,60,40,50
         *  ^     ^
         * 
         * 基准值换
         * 10,20
         * 第一轮交换
         * 10,20
         *  ^  ^
         * 左右哨兵相遇，置换相遇位置与基准值
         * 10,20
         * ^
         * ^
         * 第一轮交换结束
         * 10,20
         * 
         * 基准值交换
         * 0 1=>
         * 0 -1(left>right直接返回)
         * 1 1
         * 
         * 1 1=>
         * 1 0(left>right直接返回)
         * 2 1(left>right直接返回)
        */
        const quick_sort = (arr, left, right) => {
            if (!arr.length || left > right) {
                console.log(`return left-${left}|right-${right}`);

                return;
            }
            console.log(`left-${left}|right-${right}`);
            console.log(`baseArr|${JSON.stringify(arr)}`);

            let base = arr[left];//基准值
            console.log(`base-${base}|baseIndex-${left}`);

            let i = left;
            let j = right;
            while (i < j) {
                console.log(`arr[i]-${arr[i]}|arr[j]-${arr[j]}`);
                // 因为是需要升序，基准值右侧需要比基准值大(包括等于)，从右往左找比基准值小的，找到后暂停，等待与从左往右找到比基准值大的值交换
                while (arr[j] >= base && i < j) {
                    j--;
                }
                // 找到从左往右找到比基准值大的值,当 arr[i] 比基准值小(包括等于)，则一直循环
                while (arr[i] <= base && i < j) {
                    i++;
                }
                console.log(`i-${i}|j-${j}`);
                if (i < j) {
                    // 交换左右,es6 解构赋值
                    [arr[i], arr[j]] = [arr[j], arr[i]];
                    // let temp=arr[i];
                    //  arr[i]=arr[j];
                    //  arr[j]=temp;
                }
                console.log(`inside ${JSON.stringify(arr)}`);

            }
            console.log(`i-${i}`);

            // 左右哨兵相遇，此时相遇位置值与基准值互换
            arr[left] = arr[i];
            arr[i] = base;
            console.log(`outside ${JSON.stringify(arr)}`);
            quick_sort(arr, left, i - 1);
            quick_sort(arr, i + 1, right)

        }
        quick_sort(arr, 0, arr.length - 1);
        console.log(arr);
        /**
         * 至于为什么需要先从右往左遍历，主要是先后顺序会影响升序降序的顺序，考虑这样的一个例子
         * 原数组：[3,7,4,5,8,6,2]
         * 设置基准值为左侧第一位3，
         * 
         * 若从左往右遍历，
         * 第一轮交换
         * 先寻找比基准值大的，找到7；后从右往左，找到比基准值小的2，
         * [3,7,4,5,8,6,2]
         *    ^         ^ 
         * 第一轮交换后数组
         * [3,2,4,5,8,6,7]
         *    ^         ^       
         * 第二轮交换
         * 先寻找比基准值大的，找到4；后从右往左，遇到4，停止寻找(即需满足i<j)
         * [3,2,4,5,8,6,7]
         *      ^
         *      ^
         * 此时进行基准值与边界值的交换
         * 第二轮交换后数组
         * [4,2,3,5,8,6,7]
         *  ^   ^
         * 此时可以看到，基准值左侧的部分数组降序了，不符合整体升序要求
         * 
         * 
         * 原数组：[3,7,4,5,8,6,2]
         * 若从右往左遍历，
         * 第一轮交换
         * 先寻找比基准值小的，找到2；后从左往右，找到比基准值大的7，
         * [3,7,4,5,8,6,2]
         *    ^         ^
         * 第一轮交换后数组
         * [3,2,4,5,8,6,7]
         *    ^         ^
         * 第二轮交换
         * 先寻找比基准值小的，找到2；后从左往右，遇到2，停止寻找(即需满足i<j)
         * [3,2,4,5,8,6,7]
         *    ^
         *    ^
         * 此时进行基准值与边界值的交换
         * 第二轮交换后数组
         * [2,3,4,5,8,6,7]
         *  ^ ^
         * 此时可以看到，基准值左侧的部分数组是升序，符合整体升序要求
        */
    </script>
</body>

</html>